package com.liyunhan.SortAlgorithm;

import java.util.ArrayList;

/**
 * @Description: ================快速排序改进(基于递归)================
 * 三平均分区法 : 与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为枢轴，
 * 而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为枢轴。
 * @Author: Liyunhan
 * @Date: 2021/10/19 21:29
 */
public class QuickSortRecursionImprovement extends AlgorithmAbs {

    public QuickSortRecursionImprovement(ArrayList<Double> arrayList) {
        super(arrayList);
    }

    @Override
    public void executeAlgorithm(int... ints) {
        //可变形参要求只能没有或者两个值
        if (ints.length != 2) {
            System.out.println("输入参数只能是0个或者两个!");
            System.exit(0);
        }

        double pivot;
        //左右指针
        int i = ints[0], j = ints[1];
        if (i < j) {
            //每次选取待排数组最左边、最右边和最中间的三个元素的中间值作为中轴
            pivot = selectKey(i, j);
            //一趟快速排序, 实现数组中小于枢轴(pivot)的关键字放左边, 大于枢轴的关键字放右边
            /*
            编译器优化后做了自动装箱处理，var0 = Integer.valueOf(100);
            所以i1指向了Integer.valueOf(100)这个新产生的对象，所以最后和值传递的效果一样，
            不会改变调用该方法的参数的值。
             */
            i = QuickSortNonRecursion.onceQuickSort(i, j, arrayList);

            //将枢轴(pivot)放到最终位置
            arrayList.set(i, pivot);
            executeAlgorithm(ints[0], i - 1);
            executeAlgorithm(i + 1, ints[1]);
        }
    }

    /**
     * 在三个数中选择中位数枢轴, 此处实现为将arraylist中的这三个数按顺序
     * 放入i, mid, j位置上 (值 mid < i < j) -->i为中值
     *
     * @param i
     * @param j
     * @return
     */
    private double selectKey(int i, int j) {
        int mid = i + (j - i) / 2;
        if (arrayList.get(mid) > arrayList.get(i)) {
            swap(mid, i);
        }
        if (arrayList.get(mid) > arrayList.get(j)) {
            swap(mid, j);
        }
        if (arrayList.get(i) > arrayList.get(j)) {
            swap(i, j);
        }
        //i为中值
        return arrayList.get(i);
    }

    /**
     * 交换函数
     *
     * @param x1
     * @param x2
     */
    private void swap(int x1, int x2) {
        double temp = arrayList.get(x1);
        arrayList.set(x1, arrayList.get(x2));
        arrayList.set(x2, temp);
    }
}
